﻿#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<algorithm>
using namespace std;

//2
/*

你有一个背包，最多能容纳的体积是V。
现在有n个物品，第i个物品的体积为𝑣𝑖 vi,价值为
𝑤𝑖 wi。
（1）求这个背包至多能装多大价值的物品？
*/
const int N = 1010;
int n, W;
//int w[N], v[N];
int w[N] = { 0, 2, 2, 6, 5, 4 };
int v[N] = { 0, 6, 3, 5, 4, 6 };
int f[N][N];//f[i][j]表示从前i件物品中选花费不超过j能取到的最大价值
int x[N];//解向量
int main()
{
	n = 5, W = 10;


	//初始化f[0][0]=0表示前0件物品中选花费不超过0能取到的最大价值为0
	for (int i = 1; i <= n; ++i)
	{
		for (int j = W; j >= w[i]; --j)
		{
			//            不选i          选
			f[i][j] = max(f[i - 1][j], f[i - 1][j - w[i]] + v[i]);
		}
	}

	int j = W; // 当前剩余容量
	for (int i = n; i >= 1; --i)
	{
		if (j >= w[i] && f[i][j] == f[i - 1][j - w[i]] + v[i]) //反推
		{
			x[i] = 1; // 选中该物品
			j -= w[i]; // 更新剩余容量
		}
	}


	cout << "最优总价值：";
	cout << f[n][W] << endl;
	cout << "选取方案为：";
	// 输出选取方案
	for (int i = 1; i <= n; ++i)
	{
		if (!x[i])continue;
		cout << i;
		cout << ' ';
	}
	cout << endl;
	return 0;
}




//1
/*
2.7.1
实验1
求解一个序列中出现次数最多的元素问题
*/
//
//
//const int N = 1010;
//
//int n;
//int a[N];
//int maxn = 0;
//int maxa;
//int main()
//{
//	//输入
//	cin >> n;
//	for (int i = 1; i <= n; ++i)
//	{
//		cin >> a[i];
//	}
//
//
//	sort(a + 1, a + 1 + n);
//
//	int pred = a[0];
//	int num = 1;
//	for (int i = 1; i <= n; ++i)
//	{
//		//同一个数时，统计次数
//		while(i < n && a[i] == pred)
//		{
//			num++;
//			i++;
//		}
//		if (num > maxn)
//		{
//			maxn = num;
//			maxa = pred;
//		}
//		//每次统计次数前初始化
//		pred = a[i];
//		num = 1;
//	}
//	cout << maxa << endl;
//
//	return 0;
//}